#include <stdio.h>
#include <stdlib.h>

/*
 * 循环队列 2016/5/20 11:26
 */

/*

循环队列 :	规定循环队列最多只能有MaxSize-1个队列元素


	在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，

	一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。

	自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。

	这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，



	在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。

	为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，

	队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

*/

struct queue
{
  int * queue;
  int front, rear;
  int max_size;
};

void init(struct queue * src, int max)
{
  src->queue = (int *) malloc (sizeof(int) * max);
  if (!src->queue) {
    printf("init malloc fail.\n");
    exit(0);
  }
  
  src->max_size = max;
  src->front = src->rear = 0;
}

int empty(struct queue * src)
{
  if (src->front == src->rear)
    return 1;
  else
    return 0;
}

int full(struct queue * src)
{
  if (src->front == (src->rear + 1) % src->max_size) // 判断循环链表是否满，留一个预留空间不用 
    return 1;
  else
    return 0;
}

void enqueue(struct queue * src, int value)
{
  if (full(src)) {
    printf("queue was full.\n");
    return ;
  }

  src->queue[src->rear] = value;
  src->rear = (src->rear + 1) % src->max_size;  // 取余，当src->rear+1=max_size时，又转回到0.
}

void dequeue(struct queue * src)
{
  if (empty(src)) {
    printf("queue is empty.\n");
    return ;
  }
  
  src->queue[src->front] = -1;
  src->front = (src->front + 1) % src->max_size;
  //src->front++;
}

void display(struct queue * src)
{
  int i;
  
  printf("display: ");
  for (i = src->front; i < src->max_size; i++) {
    printf(" %d ", src->queue[i]);
  }
  printf("\n\n");
}

void display_all(struct queue * src)
{
  int i;
  
  printf("display all: ");
  for (i = 0; i < src->max_size; i++) {
    printf(" %d ", src->queue[i]);
  }
  printf("\n\n");
}

void clean(struct queue * src)
{
  if (src->queue != NULL) {
    free(src->queue);
    src->queue = NULL;
    src->front = 0;
    src->rear  = 0;
    src->max_size = 0;
  }
}

int main()
{
  struct queue queue;
  int max_size = 10;

  init(& queue, max_size);
  enqueue(& queue, 1);
  enqueue(& queue, 2);
  enqueue(& queue, 3);
  enqueue(& queue, 4);
  enqueue(& queue, 5);
  enqueue(& queue, 6);
  display(& queue);	// 1  2  3  4  5  6  0  0  0  0 

  dequeue(& queue);	// del 1
  dequeue(& queue);	// del 2
  display(& queue);	// 3  4  5  6  0  0  0  0

  enqueue(& queue, 11);
  enqueue(& queue, 22);
  enqueue(& queue, 33);
  enqueue(& queue, 44);
  enqueue(& queue, 55);
  enqueue(& queue, 66);	// queue was full.
  display(& queue);		// 3  4  5  6  11  22  33  44 
  display_all(& queue);	// 55  -1  3  4  5  6  11  22  33  44

  dequeue(& queue);		// del 3
  dequeue(& queue);		// del 4
  display(& queue);		// 5  6  11  22  33  44
  display_all(& queue);	// 55  -1  -1  -1  5  6  11  22  33  44

  dequeue(& queue);		// del 5
  dequeue(& queue);		// del 6
  dequeue(& queue);		// del 11
  dequeue(& queue);		// del 22
  dequeue(& queue);		// del 33
  dequeue(& queue);		// del 44
  display(& queue);		// 55  -1  -1  -1  -1  -1  -1  -1  -1  -1
  display_all(& queue);	// 55  -1  -1  -1  -1  -1  -1  -1  -1  -1 

  enqueue(& queue, 1);
  enqueue(& queue, 2);
  enqueue(& queue, 3);
  enqueue(& queue, 4);
  enqueue(& queue, 5);
  enqueue(& queue, 6);
  display(& queue);		// 55  1  2  3  4  5  6  -1  -1  -1
  display_all(& queue);	// 55  1  2  3  4  5  6  -1  -1  -1 


  enqueue(& queue, 11);
  enqueue(& queue, 22);
  enqueue(& queue, 33);	// queue was full.
  enqueue(& queue, 44);	// queue was full.
  enqueue(& queue, 55);	// queue was full.
  enqueue(& queue, 66);	// queue was full.
  display(& queue);		// 55  1  2  3  4  5  6  11  22  -1 
  display_all(& queue);	// 55  1  2  3  4  5  6  11  22  -1 

  dequeue(& queue);		// del 55
  dequeue(& queue);		// del 1
  display(& queue);		// 2  3  4  5  6  11  22  -1
  display_all(& queue);	// -1  -1  2  3  4  5  6  11  22  -1

  enqueue(& queue, 83);
  enqueue(& queue, 84);
  enqueue(& queue, 85);	// queue was full.
  enqueue(& queue, 86);	// queue was full.
  display(& queue);		// 2  3  4  5  6  11  22  83 
  display_all(& queue);	// 84  -1  2  3  4  5  6  11  22  83

  enqueue(& queue, 93);	// queue was full.
  enqueue(& queue, 96);	// queue was full.
  display(& queue);		// 2  3  4  5  6  11  22  83
  display_all(& queue);	// 84  -1  2  3  4  5  6  11  22  83

  clean(& queue);
}
